package com.jxb.seven;

/**
 *示例 1：
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 * i为5行，j为12列
 * i:对应数组中的元素，j当前所需计算的和
 * //dp[i-1][j]不使用nums[i-1]，dp[i-1][j-nums[i-1]]使用了nums[i-1]
 * dp数组：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]
 */
public class PartitionEqSubsetSum1_416 {

    /*二维DP数组的实现*/
    public boolean canPartition2(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        if (n == 2) {
            return nums[0] == nums[1];
        }

        //sum统计数组元素和,maxNum记录数组最大元素数值
        int sum = 0,maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum,num);
        }

        //sum为奇数的话，是不可能分给2个相等的子集
        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;
        //数组最大值大于数据元素和的一半，是不可能分为和相等的两个子集
        if (maxNum > target) {
            return false;
        }
        //eg:nums = [1,5,11,5]
        //target=2
        //sum=22
        //boolean[][] dp = new boolean[5][3]
        //dp[i][j]代表：
        //定义dp数组
        boolean[][] f = new boolean[n+1][target+1];
        //i:对应数组中的元素，j当前所需计算的和
        f[0][0] = true;
        for (int i = 1;i<=n;i++) {
            for (int j = 1;j<=target;j++) {
                if (nums[i] >= target) {
                    return nums[i] > target ? false : true;
                }
                if (j >= nums[i-1]) {
                    //dp[i-1][j]不使用nums[i-1]，dp[i-1][j-nums[i-1]]使用了nums[i-1]
                    //f[1][0] = f[0][0] || f[0][0] = true
                    f[i][j] = f[i-1][j-nums[i-1]] || f[i-1][j];
                }else {
                    f[i][j] = f[i-1][j];
                }
            }
        }
        return f[n][target];
    }

    public boolean canPartition(int[] nums) {
        int n = nums.length;
        /*数组元素只有0个或者1个，直接返回false*/
        if (n < 2) {
            return false;
        }
        /*数组元素只有2个，直接判断*/
        if(n ==2){
            return nums[0] == nums[1]? true : false;
        }
        /*sum统计数组元素和，maxNum记录数组最大数值元素*/
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        /*sum为奇数，是不可能分为和相等的两个子集*/
        if (sum % 2 != 0)  return false;
        int target = sum / 2;
        /*数组最大数值大于数组元素和的一半，是不可能分为和相等的两个子集*/
        if (maxNum > target) {
            return false;
        }
        //定义dp数组
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i<n;i++) {
            int num = nums[i];
            if(num >= target) return num > target ? false : true;
            for (int j = target;j>=num;--j) {
                dp[j] = dp[j] || dp[j-num];
            }
        }
        return dp[target];
    }

}
